logspace reducible

Definition

A language $B$ is logspace reducible to language $C$, denoted $B \leq_l C$, if there is a function $f: \{0,1\}^* \to \{0,1\}^*$ that is implicitly logspace computable and $x \in B$ iff $f(x) \in C$ for every $x \in \{0,1\}^*$

See also

• compare Karp reduction
• many-to-one reducibility
• Levin reduction

References

1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 88.